#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int size;
void display();
void append();
void extend();
void insert();
void remove1();
void pop();
void index1();
void count();
void sort();
void reverse();

struct node{
int data;
struct node *next;
}*p, *p2;


void main()
{
system("clear");
printf("How many elements do you want to enter in the initial main list ? \n");
scanf("%d", &size);
printf("Enter the elements of the list : \n");
int ele;
int counter;
for(counter=0;counter<size;counter++)
	{struct node *temp,*q;
	temp= (struct node *)calloc(1,sizeof(struct node));
	printf("Enter element %d : ", counter+1);
	scanf("%d", &ele);
        temp->data=ele;
        q=(struct node *)p;
        if (p == NULL)
        	{
    		p=temp;
    		p->next =NULL;
     		}
  	else
     		{
      		while( q->next != NULL)
       		q=q->next;
       		q->next =temp;
       		q=temp;
       		q->next=NULL;
   		}
	}

char ch='y';
while(ch=='y')
{system("clear");
display();
printf("\nYou can perform following functions on the list : \n1. Append\n2. Extend\n3. Insert\n4. Remove\n5. Pop\n6. Index\n7. Count\n8. Sort\n9. Reverse\n10. Display\n\nEnter the serial no. of function you want to perform or press 0 to exit : ");
int opt;
scanf("%d", &opt);
switch(opt)
	{case 0: exit(0);
	case 1 :append();
		break;
	case 2: extend();
		break;
	case 3: insert();
		break;
	case 4: remove1();
		break;
	case 5: pop();
		break;
	case 6: index1();
		break;
	case 7: count();
		break;
	case 8: sort();
		break;
	case 9: reverse();
		break;
	case 10: display();
		break;
	default: printf("Invalid Input!\n");
	}

fflush(stdin);
printf("Do you want to perform more operations? Enter 'y' for yes or any other character to exit.\n");
scanf("%s", &ch);
if(ch!='y')
printf("Thanks for using the program. \n");
}

}

void display()
{struct node* r;
r=p;
if(r==NULL)
printf("The current list is : \n[]\n");
else
	{printf("The current list is : \n[");
      	printf(" %d ",r->data);
      	r=r->next;
	while(r!=NULL)
		{
		printf(", %d ", r->data);
		r=r->next;
		}
	printf("]\n");
    	}
}

void append()
{
struct node* r, *temp;
r=p;
printf("Enter the element you want to append : ");
int num;
scanf("%d", &num);
temp= (struct node *)calloc(1,sizeof(struct node));
temp->data= num;
while( r->next != NULL)
r=r->next;
r->next =temp;
r=temp;
r->next=NULL;
size=size+1;
display();
}

void extend()
{
printf("Enter the no of elements in second list to extend the main list : ");
int size2;
scanf("%d", &size2);

printf("Enter the elements of second list : \n");
int ele;
int counter;
struct node* q;

for(counter=0;counter<size2;counter++)
	{
	struct node *temp;
	temp=(struct node *)calloc(1,sizeof(struct node));
	printf("Enter element %d : ", counter+1);
	scanf("%d", &ele);
        temp->data=ele;
        q=(struct node *)p2;
        if (p2 == NULL)
        	{
    		p2=temp;
    		p2->next =NULL;
     		}
  	else
     		{
      		while( q->next != NULL)
       		q=q->next;

       		q->next =temp;
       		q=temp;
       		q->next=NULL;
   		}
	}
struct node* y;
struct node *r;
y=p2;
if(y==NULL)
printf("List you have entered is : \n[]\n");
else
	{printf("The current list is : \n[");
	printf(" %d ",y->data);
      	y=y->next;
	while(y!=NULL)
		{
		printf(", %d ", y->data);
		y=y->next;
		}
	printf("]\n");
    	}
struct node* z;
z=p;
int i;
for(i=0; i<size-1;i++)
z=z->next;
r=p2;
z->next=r;
size=size+size2;
display();
}

void insert()
{
printf("Enter the element you want to insert : ");
int num;
scanf("%d", &num);
printf("Enter the position where you want to insert an element : ");
int pos;
scanf("%d", &pos);
if(pos<1 || pos>size+1)
printf("Invalid position!\n");
else
	{struct node *temp, *z, *y;
	z=p;
	y=p;	
	int i,j;
	temp= (struct node *)calloc(1,sizeof(struct node));
	temp->data= num;
	if(pos==1)
	{temp->next=z;
	p=temp;
	}
	else
	{
	for(i=1; i<=pos-1; i++)
	z=z->next;
	temp->next=z; 
	for(j=1; j<pos-1; j++)
	y=y->next;
	y->next=temp;
	}
	}
size=size+1;
display();
}

void remove1()
{
int flag3=0;
printf("Enter the element you want to remove : ");
int num;
scanf("%d", &num);
struct node *z, *y;
z=p;
y=p->next;
if(z->data==num)
	{free(z);
	p=p->next;
	flag3=1;
	}
else
	{
	for(;z->next!=NULL; z=z->next, y=y->next)
		{if(z->next->data==num)
			{free(z->next);
			z->next=y->next;
			flag3=1;
			break;
			}
	
		}
	}
if(flag3==0)
printf("No such element! \n");
size=size-1;
display();
}

void pop()
{
printf("Enter the index no. of element you want to remove : ");
int pos;
scanf("%d", &pos);
struct node *z, *y;
z=p;
y=p;
if(pos<1 || pos>size)
printf("Invalid position!\n");
else
	{
	if(pos==1)
	{printf("The element which has been removed is %d.\n", p->data);	
	p=p->next;}
	else
	{int i,j;
	for(i=1; i<pos-1; i++)
	z=z->next;
	printf("The element which has been removed is %d.\n", z->next->data);	
	for(j=1; j<=pos-1; j++)
	y=y->next;
	z->next=y->next;
	}	
	}
size=size-1;
display();
}

void index1()
{
printf("Enter the element whose index of first occurence you want : \n");
int num;
scanf("%d", &num);
int k;
int pos;
int flag4=0;
struct node *z;
z=p;
for(k=0; z!=NULL; k++, z=z->next)
	{if(z->data==num)
	{pos=k;
	flag4=1;
	break;
	}
	}
if (flag4==0)
printf("%d is not there in the list.\n", num);
else
printf("First occurence of this elements is at position : %d\n", pos+1);
}

void count()
{
printf("Enter the element whose count you want : ");
int num;
scanf("%d", &num);
struct node* z;
z=p;
int count=0;
for(; z!=NULL;z=z->next)
	{if(z->data==num)
		count++;
	}
printf("No. of occurences of %d is %d.\n", num, count);
}
void sort()
{
     struct node *a,*b;
  int temp;  
a=p;
  for(;a->next!=NULL;a=a->next)
  {
    for(b=a->next;b!=NULL;b=b->next)
    {
      if(b->data < a->data)
      {
       temp=a->data;
        a->data=b->data;
        b->data=temp;   
      }
    }
  }
printf("The list has been sorted.\n");
display();
}

/*
void swap(struct node *z, struct node *y)
{
display();
struct node *temp;
temp= z->next;
z->next= z->next->next;
temp->next=z;
y->next=temp;
}
void swap2(struct node *z)
{
display();
struct node *temp;
temp= z->next;
z->next= z->next->next;
temp->next=z;
p=temp;
}


void sort()
{
struct node *z, *prev;

int i, j;
for(i=1; i<size; i++)
	{z=p;
	prev=z;
	for(j=1; j<size; j++)
		{
display();
		if(z->data > z->next->data)
			{
display();
			if(j==1)
				{
				swap2(z);}
			else
				{	
				swap(z, prev);}
			}
		
		prev=z;
		
		z=z->next;
		}

	}
printf("The list has been sorted.\n");
display();
}
/*
void sort()
{
int i, j;
struct node *z, *a, *b, *c, *d;
z=p;
for(i=1; i<size; i++)
	{ a= (struct node*)NULL;
	b=z;
	c=z->next;
	d=c->next;
	for(j=1; j<= (size-i) ; j++)
		{ if(b->data > c->data)
			{display();
			b->next=d;
			c->next=b;
			if(z==b) z=c;
			a->next=c;
			a=c;
			c=b->next;
			if (d->next !=NULL) d=d->next;
			else d= (struct node*) NULL;
			}
		else
			{ display();
			a=b;
			b=c;
			c=d;
			if (d->next !=NULL) d=d->next;
			else d= (struct node*) NULL;
			}
		}
	}
}	
*/
void reverse()
{
struct node *z,*y,*w;
z=p;
y=NULL;
while(z!=NULL)
{
w=y;
y=z;
z=z->next;
y->next=w;
}
p=y;
printf("The list has been reversed.\n");
display();
}
